package org.blogwu.learn.leetcode.链表;

public class _141_环形链表_快慢指针 {

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5);


        ListNode listNode4 = new ListNode(4, listNode5);
        ListNode listNode3 = new ListNode(3, listNode4);
        ListNode listNode2 = new ListNode(2, listNode3);
        ListNode listNode1 = new ListNode(1, listNode2);
//        listNode1.next = listNode1;

        _141_环形链表_快慢指针 cc = new _141_环形链表_快慢指针();
        System.out.println(":::" + cc.hasCycle(listNode1));


    }

    /**
     * 快慢指针
     * 快指针走两步，慢指针走一步
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        if (head.next == null) return false;
        ListNode snow = head;
        int i = 0;
        while (true) {
            head = head.next;
            if (head == null) {
                return false;
            }
            if (i > 2) {
                snow = snow.next;
                if (head.val == snow.val) {
                    return true;
                }
                i = 0;
            } else {
                i++;
            }
        }
    }
}
